Thực đơn
Cây_tìm_kiếm_nhị_phân Các phép toán trên BSTViệc tìm một khóa trên BST có thể thực hiện nhờ đệ quy. Chúng ta bắt đầu từ gốc. Nếu khóa cần tìm bằng khóa của gốc thì khóa đó trên cây, nếu khóa cần tìm nhỏ hơn khoa ở gốc, ta phải tìm nó trên cây con trái, nếu khóa cần tìm lớn hơn khóa ở gốc, ta phải tìm nó trên cây con phải. Nếu cây con (trái hoặc phải) là rỗng thì khóa cần tìm không có trên cây.
Giả mã
Search_binary_tree(node, key);
if node is Null then return None; /* key not found */ if key < node.key: return search binary_tree(node.left, key); else if key > node.key return search_binary_tree(node.right, key) else /* key is equal to node key */ return node.value; # found key
Mã Python:
def search_binary_tree(node, key): if node is None: return None # key not found if key < node.key: return search_binary_tree(node.leftChild, key) elif key > node.key: return search_binary_tree(node.rightChild, key) else: # key is equal to node key return node.value # found key
Thời gian tìm kiếm trung bình là O(log 2n), và là O(n) khi cây là không cân bằng chỉ là một danh sách liên kết.
Phép chèn bắt đầu giống như phép tìm kiếm; Nếu khóa của gốc khác khóa cần chèn ta tìm nó trong cây con trái hoặc phải. Nếu cây con trái hoặc phải tương ứng là rỗng (không tìm thấy) thì thêm một nút và gán cho nút ấy khóa cần chèn.
Sau đây là mã trong C++:
void InsertNode(struct node *&treeNode, struct node *newNode){ //Inserts node pointered by "newNode" to the subtree started by "treeNode" if (treeNode == NULL) treeNode = newNode; //Only changes "node" when it is NULL else if (newNode->value < treeNode->value) InsertNode(treeNode->left, newNode); else InsertNode(treeNode->right, newNode);}
Mã Python:
def binary_tree_insert(node, key, value): if node is None: return TreeNode(None, key, value, None) if key == node.key: return TreeNode(node.left, key, value, node.right) if key < node.key: return TreeNode(binary_tree_insert(node.left, key, value), node.key, node.value, node.right) else: return TreeNode(node.left, node.key, node.value, binary_tree_insert(node.right, key, value))
Xét các trường hợp sau
Cũng có thể tìm nút tiền nhiệm hoặc nút kế vị đổi chỗ nó với nút cần xóa và sau đó xóa nó. Vì các nút kiểu này có ít hơn hai con nên việc xóa nó được quy về hai trường hợp trước.
Sau đây là mã C++
void DeleteNode(struct node*& node) { if (node->left == NULL) { struct node* temp = node; node = node->right; delete temp; } else if (node->right == NULL) { struct node* temp = node; node = node->left; delete temp; } else { // In-Order predecessor(right most child of left subtree) // Node has two children - get max of left subtree struct node** temp = &(node->left); // get left node of the original node // find the right most child of the subtree of the left node while ((*temp)->right != NULL) { temp = &((*temp)->right); } // copy the value from the right most child of left subtree to the original node node->value = (*temp)->value; // then delete the right most child of left subtree since it's value is // now in the original node DeleteNode(*temp); }}
Mã python:
def findMin(self): ''' Finds the smallest element that is a child of *self* ''' current_node = self while current_node.left_child: current_node = current_node.left_child return current_nodedef replace_node_in_parent(self, new_value=None): ''' Removes the reference to *self* from *self.parent* and replaces it with *new_value*. ''' if self == self.parent.left_child: self.parent.left_child = new_value else: self.parent.right_child = new_value if new_value: new_value.parent = self.parentdef binary_tree_delete(self, key): if key < self.key: self.left_child.binary_tree_delete(key) elif key > self.key: self.right_child.binary_tree_delete(key) else: # delete the key here if self.left_child and self.right_child: # if both children are present # get the smallest node that's bigger than *self* successor = self.right_child.findMin() self.key = successor.key # if *successor* has a child, replace it with that # at this point, it can only have a *right_child* # if it has no children, *right_child* will be "None" successor.replace_node_in_parent(successor.right_child) elif self.left_child or self.right_child: # if the node has only one child if self.left_child: self.replace_node_in_parent(self.left_child) else: self.replace_node_in_parent(self.right_child) else: # this node has no children self.replace_node_in_parent(None)
Khi một cây tìm kiếm nhị phân được tạo ra, tất cả các nút có thể được duyệt theo thứ tự giữa nhờ duyệt đệ quy cây con bên trái, in nút đang duyệt, rồi duyệt đệ quy cây con bên phải, tiếp tục làm như vây với mỗi nút của cây trong quá trình đệ quy. Với mọi cây nhị phân, cây có thể được duyệt theo thứ tự trước() hoặc theo thứ tự sau(), cả hai cách đều hữu dụng với cây tìm kiếm nhị phân.
Đoạn mã cho duyệt theo thứ giữa được viết dưới đây với C++:
void traverse_binary_tree(struct node* n){ if(n==null) //Cay rong return NULL; else { traverse_binary_tree(n->left); //Duyet cay con trai theo thu tu giua printf("%d",n.key); //Tham nut traverse_binary_tree(n->right); //Duyet cay con phai theo thu tu giua }}
Phép duyệt có độ phức tạp tính toán là Ω(n), vì nó phải duyệt qua tất cả các nút. Độ phức tạp trên cũng là O("n").
Một cây tìm kiếm nhị phân có thể được sử dụng như một giải thuật sắp xếp đơn giản nhưng hiểu quả. Giống như heapsort, chúng ta chèn tất cả các giá trị chúng ta muốn sắp xếp vào một cây tìm kiếm nhị phân và in ra kết quả theo thứ tự:
def build_binary_tree(values): tree = None for v in values: tree = binary_tree_insert(tree, v) return treedef get_inorder_traversal(root): ''' Returns a list containing all the values in the tree, starting at *root*. Traverses the tree in-order(leftChild, root, rightChild). ''' result = [] traverse_binary_tree(root, lambda element: result.append(element)) return result
Trường hợp xấu nhất của build_binary_tree
có độ phức tạp là Θ ( n 2 ) {\displaystyle \Theta (n^{2})} —nếu nhập vào một dãy giá trị đã sắp xếp, cây nhị phân tạo thành sẽ không có các nút trái. Ví dụ, traverse_binary_tree([1, 2, 3, 4, 5])
tạo thành cây (1 (2 (3 (4 (5)))))
.
Có một vài cách để vượt qua trường hợp này với các cây nhị phân đơn giản; cách đơn giản nhất là cây tìm kiếm nhị phân tự cân bằng. Với thủ tục này được sử dụng với cây nhị phân tự cân bằng, trường hợp xấu nhất sẽ có độ phức tạp là O(nlog n).
Thực đơn
Cây_tìm_kiếm_nhị_phân Các phép toán trên BSTLiên quan
Cây trồng biến đổi gen Cây táo nở hoa Cây tìm kiếm nhị phân Cây tre trăm đốt Cây thường xanh Cây thuốc Cây trường sinh vằn Cây thiêng Cây Trường II Cây ThịTài liệu tham khảo
WikiPedia: Cây_tìm_kiếm_nhị_phân http://cg.scs.carleton.ca/~dana/pbst http://www.24bytes.com/Binary-Search-Tree.html http://aspn.activestate.com/ASPN/Cookbook/Python/R... http://www.goletas.com/solutions/collections/ http://cslibrary.stanford.edu/110/ http://nova.umuc.edu/~jarc/idsv/lesson1.html http://webpages.ull.es/users/jriera/Docencia/AVL/A... http://www.nist.gov/dads/HTML/binarySearchTree.htm... http://www.algolist.net/Data_structures/Binary_sea... http://jdserver.homelinux.org/wiki/Binary_Search_T...